package com.haidechizi.leetcode;

public class _33_搜索旋转排序数组 {

    public int search(int[] nums, int target) {
        if(nums == null || nums.length == 0) {
            return -1;
        }
        int i = 0;
        while (i < nums.length - 1 && nums[i] < nums[i + 1]) {
            i++;
        }
        if (nums[0] > target) {
            return divideSearch(nums, i + 1, nums.length - 1, target);
        }
        return divideSearch(nums, 0, i, target);
    }

    public int divideSearch(int[] nums, int start, int end, int target) {
        if (start > end) {
            return -1;
        }
        int middle = (start + end) / 2;
        if (nums[middle] == target) {
            return middle;
        } else if (nums[middle] > target) {
            return divideSearch(nums, start, middle-1, target);
        } else {
            return divideSearch(nums, middle+1, end, target);
        }

    }

    public static void main(String[] args) {
        new _33_搜索旋转排序数组().search(new int[]{4, 5, 6, 7, 0, 1, 2}, 3);
    }
}
